package com.demo.java.OD301_350.OD306;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【寻找最大价值的矿堆(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146101733
 */
public class OdMain {
    // 方向数组：上、下、左、右四个方向的移动
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    // 定义矩阵的行数和列数
    private static int rows, cols;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 用于读取输入的矩阵数据
        StringBuilder input = new StringBuilder();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.trim().isEmpty()) {
                break;  // 输入结束条件：遇到空行
            }
            input.append(line).append("\n");  // 将每一行输入存储在字符串中
        }

        // 将输入的字符串按行分割成字符串数组
        String[] lines = input.toString().split("\n");
        // 获取矩阵的行数和列数
        rows = lines.length;
        cols = lines[0].length();

        // 初始化矩阵，将输入的每个字符转换为整数存入矩阵
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = Character.getNumericValue(lines[i].charAt(j));
            }
        }

        // 初始化访问标记数组，标记每个位置是否已经访问过
        boolean[][] visited = new boolean[rows][cols];

        int maxValue = 0;  // 用于存储最大值

        // 遍历矩阵中的每个元素
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果当前元素是非零并且没有被访问过，进行深度优先搜索（DFS）
                if (matrix[i][j] > 0 && !visited[i][j]) {
                    int value = dfs(i, j, matrix, visited);  // 计算当前区域的总值
                    maxValue = Math.max(maxValue, value);  // 更新最大值
                }
            }
        }

        // 输出最大值
        System.out.println(maxValue);
    }

    // 深度优先搜索（DFS）方法
    private static int dfs(int x, int y, int[][] matrix, boolean[][] visited) {
        // 边界检查和访问检查
        if (x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || matrix[x][y] == 0) {
            return 0;  // 如果越界、已经访问或者是空地，返回0
        }

        // 标记当前位置已经访问
        visited[x][y] = true;

        int value = matrix[x][y];  // 当前格子的值

        // 探索四个方向（上、下、左、右）
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];  // 计算新位置的x坐标
            int newY = y + direction[1];  // 计算新位置的y坐标
            value += dfs(newX, newY, matrix, visited);  // 递归搜索新位置
        }

        return value;  // 返回当前区域的总价值
    }
}
